Cốt truyện trong game được kể lại hoàn toàn thông qua những đoạn phim cắt cảnh và điện ảnh, với các thông tin bổ sung được tìm thấy trong hướng dẫn sử dụng Warcraft III. Chiến dịch tự chia thành 5 phần, với màn đầu tiên là phần chơi hướng dẫn, và những chủng tộc khác kể lại câu chuyện theo quan điểm của loài Human xứ Lordaeron, loài Undead Scourge, loài Orc, và loài Night Elves, theo thứ tự đó.

Trò chơi mở ra với nhà lãnh đạo của phe Orc tên là Thrall đang thức giấc từ một cơn ác mộng cảnh báo cho anh biết về sự trở lại của Burning Legion.[5] Sau cuộc chạm trán ngắn ngủi với một người đàn ông được biết đến với tên gọi "Nhà Tiên tri", sợ rằng giấc mơ của mình sẽ thành hiện thực hơn là một cơn ác mộng, anh ta liền dẫn lực lượng của mình thành một cuộc di dân từ Lordaeron đến vùng đất bị lãng quên Kalimdor.[6]

Trong khi đó, Paladin Uther the Lightbringer giao nhiệm vụ cho Arthas Menethil hoàng tử xứ Lordaeron, bảo vệ ngôi làng Strahnbrad khỏi tay lũ Orc bị ma quỷ kiểm soát.[7] Sau đó, Archmage Jaina Proudmoore nhập bọn cùng Arthas, cô và anh điều tra một bệnh dịch đang lây lan nhanh chóng, giết chết và biến những nạn nhân của phe người thành Undead. Arthas giết được kẻ gây ra bệnh dịch là Kel'Thuzad, trước khi chết hắn đã tiết lộ kẻ đứng sau mình là dreadlords Mal'Ganis, Arthas và Jaina đến ngôi làng Hearthglen nghỉ chân và phát hiện một binh đoàn Undead đang tiến về phía này Arthas nhờ Jaina dịch chuyển đi tìm sự giúp đỡ của Uther trong khi anh ở lại cùng với quân lính bảo vệ ngôi làng, Arthas và hàng ngũ quân lính gần như bị đập tan nếu Uther và Jaina không quay lại kịp thời. Sau đó Arthas, Uther và Jaina đến Stratholme để tiêu diệt Mal'Ganis, khi đến nơi họ nhận thấy toàn bộ cư dân ở đây đã bị lây nhiễm nên Arthas quyết định thanh trừng cả thành phố. Uther từ chối vì việc đó quá tàn nhẫn và rời đi, Jaina cũng chia tay với Arthas vì không muốn nhìn thấy anh làm điều này. Arthas bắt đầu công việc thanh trừng và chạm trán Mal'Ganis khi hắn đang thu thập linh hồn của người dân trong thành phố, Arthas kết thúc công việc nhanh hơn tên dreadlords và suýt tiêu diệt được Mal'Ganis nhưng hắn đã kịp trốn thoát và để lại lời thách thức hãy tìm gặp hắn ở Northrend. Nhà Tiên tri, sau khi cố thuyết phục các nhà lãnh đạo phe người khác chạy trốn sang vùng đất phía Tây không thành, nên đã quay sang thuyết phục Jaina đến Kalimdor.[8] Arthas đuổi theo dreadlord Mal'Ganis, là thủ lĩnh đứng đằng sau Kel'Thuzad, tới lục địa băng giá Northrend và gặp lại người bạn cũ là Muradin Bronzebeard giúp ông tìm kiếm một thanh kiếm có tên gọi là Frostmourne. Arthas bắt đầu đánh mất lý trí của mình sau khi nghe tin lực lượng của anh đã được Phái viên theo lệnh của nhà vua triệu tập họ quay về Lordaeron. Không muốn quay trở lại, anh ta bèn sai những người lính đánh thuê đốt cháy các tàu của mình để ngăn chặn quân lính rút lui, sau đó phản bội đám lính đánh thuê và sai quân của mình giết họ, khiến Muradin kinh ngạc. Arthas và Muradin cuối cùng đã tìm ra Frostmourne. Thế nhưng khi đọc những dòng chữ trên tảng đá chứa thanh kiếm Muradin mới biết được rằng thanh kiếm này đã bị nguyền rủa.[9] Arthas không quan tâm đến lời cảnh báo, và hiến dâng linh hồn của mình để có bằng được thanh kiếm. Tảng băng bị vỡ thanh kiếm Frostmourne rơi ra, Muradin bị một tảng băng hạ gục, và có thể đã chết. Arthas tiêu diệt được Mal'Ganis, bỏ lại người của mình ở căn cứ và tiến vào nơi hoang vu giá lạnh vì linh hồn của anh ta đã bị thanh kiếm đoạt mất, mà sau này mới được tiết lộ là thanh kiếm được Lich King làm ra. Ít lâu sau, Arthas trở về Lordaeron và giết cha mình là vua Terenas Menethil.

Trở thành Death Knight của chủng tộc Undead, Arthas tới gặp kẻ đứng đầu của các dreadlord là Tichondrius, hắn giao cho anh hàng loạt các "thử thách". Arthas có nhiệm vụ đi tập hợp lại các thành viên của giáo phái "Cult of the damned" sau đó khai quật di hài của Kel'Thuzad và cất vào trong bình đựng tro cốt ma thuật chứa phần tro của cha mình, được bảo vệ bởi Uther paladin đứng đầu tổ chức Silver Hand (Bàn tay bạc) và cũng là người thầy cũ của Arthas. Arthas giết Uther đoạt lấy bình tro rồi khởi hành tới Quel'thalas, vương quốc của loài High Elves. Anh ta tấn công các cổng thành và phá hủy thủ đô Silvermoon của họ, hạ sát Sylvanas Windrunner, viên thống lĩnh lực lượng bảo vệ Silvermoon (sau đó hồi sinh cô trở thành một banshee), phá hỏng di tích thiêng liêng Sunwell và hồi sinh Kel'Thuzad dưới dạng là một lich. Kel'Thuzad cho anh ta biết thông tin về Burning Legion; một đạo quân ma quỷ khổng lồ tàn phá khắp vũ trụ và hiện giờ nó đang tràn đến thế giới này. Chủ nhân thực sự của Kel'Thuzad chính là Lich King, người được tạo ra để trợ giúp cho cuộc xâm lược của Burning Legion với đội quân xác sống Scourge của hắn, nhưng thật ra hắn ta mong muốn Legion sẽ bị tiêu diệt. Arthas và Kel'Thuzad mở một cánh cổng không gian và triệu hồi chúa quỷ Archimonde và Burning Legion, sau khi Archimonde dịch chuyển đến Azeroth hắn bắt đầu cuộc thanh trừng vương quốc Lordaeron với sự kiện phá hủy thành Dalaran. Archimonde tuyên bố giờ đây Lich King không còn giá trị gì đối với Legion nữa nên giao cho Tichondrius nắm quyền điều hành quân Scourge, Arthas và Kel'Thuzad đều bị Archimonde bỏ mặc, sau khi Archimonde và Tichondrius bỏ đi Kel'Thuzad tiết lộ cho Arthas biết là Lich King đã đoán trước được điều này và đang có kế hoạch lật đổ Burning Legion.

Thrall tộc trưởng loài Orc đã đặt chân đến vùng Kalimdor, gặp gỡ Cairne Bloodhoof tộc trưởng của loài Tauren và xung đột với đoàn quân tị nạn của phe Human khi đang trên đường tìm kiếm tung tích Oracle. Nhằm tránh những cuộc giao tranh không cần thiết với phe Human, tộc Warsong và thủ lĩnh của họ là Grom Hellscream được Thrall chỉ thị đến khu rừng Ashenvale để xây dựng một khu căn cứ mới, Grom Hellscream và tộc Warsong tiến sâu vào khu rừng khai thác được một lượng lớn gỗ nhưng lại chọc giận loài Night Elves và vị á thần của họ là Cenarius vì dám tự tiện vào chặt phá rừng của họ làm tài nguyên. Bị Cenarius đánh đuổi, tộc Warsong thất thế trước sức mạnh của vị á thần, một Witch Doctor của loài Troll đã nói với Grom Hellscream rằng ông ta cảm nhận được nguồn sức mạnh phát ra từ một hồ nước trong rừng, để có được sức mạnh chống trả lại Cenarius, Grom Hellscream và tộc Warsong đã đến đó và uống nước từ hồ nước này (trước đó hồ nước đã được nhỏ máu của vị tướng của Burning Legion tên là Mannoroth do hắn muốn mượn tay loài Orc để tiêu diệt Cenarius) nhờ vậy đã giết được Cenarius nhưng lại ràng buộc tộc Warsong của mình nằm dưới sự khống chế của Burning Legion. Thrall tìm cách tới chỗ Oracle, trên thực tế là nơi Nhà Tiên tri sẽ nói cho anh ta biết về những hành động của Grom. Theo những lời chỉ dẫn của Nhà Tiên tri, Thrall và Jaina cùng hợp lực để cứu cả Grom lẫn thế giới khỏi cuộc xâm lược của Burning Legion. Họ thành công trong việc bắt giữ Grom và chữa lành anh ta khỏi sự hung bạo do ảnh hưởng từ máu của Mannoroth. Thrall và Grom bắt đầu truy tìm Mannoroth và Grom giết được hắn nhưng lại hi sinh, nhưng làm như vậy đã giải phóng được anh và tộc Warsong thoát khỏi sự kiểm soát của Mannoroth. Thrall bảo với cơ thể bất động của Grom rằng anh ta đã giải phóng cho tất cả loài Orc và rống lên báo cho Jaina và Cairne biết về cái chết của Grom.

Tyrande Whisperwind, lãnh đạo của loài Night Elves, đã phát hiện ra Human và Orc đang xâm phạm khu rừng và đổ lỗi chính họ là nguyên nhân gây ra cái chết cho Cenarius nên cô quyết định quét sạch những kẻ tị nạn này khỏi khu rừng. Tuy vậy, khi chạm trán Archimonde và Tichondrius cô nhận ra Burning Legion đã quay trở lại xâm chiếm Kalimdor. Để kháng cự lại Burning Legion, Tyrande đánh thức các Druid Elf đang ngủ say giấc, bắt đầu từ người yêu của mình là Malfurion Stormrage, trong quá trình tìm kiếm và đánh thức các Druid of the Claw dưới lòng đất họ phát hiện ra nhà tù đang giam giữ Illidan Stormrage em trai của Malfurion nên Tyrande quyết định giải phóng anh ta ra khỏi tù để có thêm đồng minh chống lại Legion mặc cho Malfurion phản đối. Sau khi được tự do Illidan đến khu rừng Fellwood bắt gặp Arthas và được hắn cho biết về "Skull of Gul'dan" đầy quyền năng đang được Tichondrius sử dụng để tha hóa khu rừng này. Phá hủy và hấp thụ sức mạnh từ chiếc đầu lâu này Illidan bị biến đổi thành chủng loài lai giữa elf và quỷ, sử dụng sức mạnh của chiếc đầu lâu Illidan đã giết được Tichondrius. Tuy nhiên khi nhìn thấy bộ dạng ma quỷ của Illidan, Malfurion đã đuổi hắn ra khỏi khu rừng và cấm hắn không bao giờ được trở lại nơi này nữa vì giờ đây hắn ta là một phần của quỷ dữ rồi. Trong khi đó, Nhà Tiên tri cho triệu tập Thrall, Jaina, Tyrande và Malfurion, và tiết lộ lý do mà Legion quay trở lại và hé lộ bản thân ông chính là Medivh người Giám hộ cuối cùng và cũng là người phản bội từ bản Warcraft: Orcs & Humans, đã quay lại để sửa chữa những tội lỗi trong quá khứ của mình. Các phe Human, Orc và Night Elves tạo thành một liên minh miễn cưỡng dưới chân núi Hyjal để cầm chân Archimonde đủ lâu để cho cái bẫy của Malfurion hoạt động, khi Archimonde bước đến chuẩn bị hấp thụ năng lượng từ cây thế giới Nordrassil nhiều tinh linh cổ xưa bay tới xung quanh Archimonde tạo thành một vụ nổ lớn tiêu diệt hắn và đạo quân của hắn tại ngọn núi Hyjal này. Hòa bình một lần nữa lại đến với xứ sở Kalimdor khi Burning Legion phải gánh lấy thất bại thảm hại.

Cội nguồn sẽ chữa lành kịp thời, cũng như toàn bộ thế giới này. Sự hy sinh đã được đền đáp. Cũng giống như orc, con người và night elves đã bỏ đi những hận thù cũ của họ và thống nhất chống lại một kẻ thù chung, bản chất tự nhiên đã nổi lên để đánh đuổi thế lực bóng tối mãi mãi. Về phần mình, tôi đã trở lại để đảm bảo rằng sẽ có một tương lai, để dạy cho thế giới rằng nếu như nó không còn cần đến người giám hộ này nữa. Niềm hy vọng cho các thế hệ tương lai luôn luôn tồn tại trong tay nhân loại. Và bây giờ nhiệm vụ của tôi đã xong, tôi sẽ thay thế mình trong vô số những huyền thoại của quá khứ.

— Blizzard Entertainment, "Eternity's End"